package com.simon.study.algorithm.string;

import org.junit.Test;

/**
 * <p>
 *
 * @author simon
 * @date 2022/7/22 6:33 上午
 */
public class Kmp {

    @Test
    public void seeSfind() {
        String s = "aaabcesfee";
        String t = "llbce";

        int p = getIndexof(s, t);
        System.out.println(p);
    }

    public static int getIndexof(String source, String target){
        if(source==null || target==null || target.length() < 1 || source.length() < target.length()){
            return -1;
        }

        char[] str1 = source.toCharArray();
        char[] str2 = target.toCharArray();

        return getIndex(str1, str2);
    }


    public static int getIndex(char[] source, char[] target){
        int[] next = getNextArray(target);

        int si = 0, ti = 0;
        while (si<source.length && ti<target.length){
            if(source[si] == target[ti]){ si++; ti++; }  // move

            else if(next[ti] == -1){ si++; } // cann't go back, move si
            else{
                ti = next[ti];               // go back and retry
            }
        }
        // ti outof bounds, matched, si outof bounds return -1
        return ti == target.length ? si-ti : -1;
    }

    public static int[] getNextArray(char[] ms){
        if(ms.length == 1){ return new int[]{-1}; }

        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;

        int i=2, cn = 0;

        while (i < next.length){
            if(ms[i-1] == ms[cn]){
                next[i++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else{
                next[i++] = 0;
            }
        }

        return next;
    }
}
